% Ejercicio "Bloques en PASCAL"
\subsection*{\fbox{\theejercicio} - Bloques en PASCAL}

Sea la gram\'atica:

\begin{center}
\begin{tabular}{|lcl|} \hline
                          &               &                                                           \\
{\em Lista-de-Sentencias} & $\rightarrow$ & {\em Sentencia}                                           \\
                          & $|$           & {\em Lista-de-Sentencias} {\bf ;} {\em Sentencia}         \\
{\em Sentencia}           & $\rightarrow$ & {\bf IDENT :=} {\em Condici\'on}                          \\
                          & $|$           & {\tt if (} {\em Condici\'on} {\tt ) then} {\em Sentencia} \\
                          & $|$           & {\tt begin} {\em Lista-de-Sentencias} {\tt end}           \\
{\em Condici\'on}         & $\rightarrow$ & {\bf TRUE}                                                \\
                          & $|$           & {\bf FALSE}                                               \\
                          & $|$           & {\bf IDENT $=$ IDENT}                                     \\
                          & $|$           & {\bf IDENT $<>$ IDENT}                                    \\
                          & $|$           & {\em Condici\'on} {\bf AND} {\em Condici\'on}             \\
                          &               &                                                    \\ \hline
\end{tabular} 
\end{center}

\begin{enumerate}[1)]
\item Demostrar que esta gram\'atica no es LL(1).
\item Construir una gram\'atica equivalente que sea LL(1) y construir para ella la tabla de an\'alisis LL(1).
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Apartado 1)

\medskip

Entre las condiciones que debe cumplir una gram\'atica para ser LL(1) se encuentran
\begin{enumerate}[a)]
\item NO ser recursiva por la izquierda.
\item NO tener reglas con prefijos comunes y el mismo antecedente. Puede observarse c\'omo la condici\'on a) es violada por la regla 2 (y tambi\'en por la 10) mientras que la condici\'on b) la violan las reglas 8 y 9.
\end{enumerate}

Apartado 2)

\medskip

Una gram\'atica equivalente ser\'{\i}a:

\begin{center}
\begin{tabular}{|l|lcl|} \hline
         &                        &               &                                              \\
{\tt 1}  & {\em ListaSentencias}  & $\rightarrow$ & {\em Sentencia ListaSentencias'}             \\
{\tt 2}  & {\em ListaSentencias'} & $\rightarrow$ & $\varepsilon$                                \\
{\tt 3}  &                        & $|$           & {\bf ;} {\em Sentencia ListaSentencias'}     \\
{\tt 4}  & {\em Sentencia}        & $\rightarrow$ & {\bf IDENT :=} {\em Condici\'on}           \\
{\tt 5}  &                        & $\rightarrow$ & {\tt if (} {\em Condici\'on} {\tt ) then}    \\
{\tt 6}  &                        & $|$           & {\tt begin} {\em ListaSentencias} {\tt end}  \\
{\tt 7}  & {\em Condici\'on}      & $\rightarrow$ & {\bf TRUE} {\em Condici\'on'}                \\
{\tt 8}  &                        & $|$           & {\bf FALSE} {\em Condici\'on'}               \\
{\tt 9}  &                        & $|$           & {\bf IDENT} {\em Comparaci\'on Condici\'on'} \\
{\tt 10} & {\em Condici\'on'}     & $\rightarrow$ & {\bf AND} {\em Condici\'on}                  \\
{\tt 11} &                        & $|$           & $\varepsilon$                                \\
{\tt 12} & {\em Comparaci\'on}    & $\rightarrow$ & {\bf = IDENT}                                \\
{\tt 13} &                        & $|$           & {\bf $<>$ IDENT}                             \\
         &                        &               &                                              \\ \hline
\end{tabular}
\end{center}

Los conjuntos CABECERA y SIGUIENTE son:

$CAB(ListaSentencias) = \{IDENT,\ IF,\ BEGIN\}$ \\
$CAB(ListaSentencias') = \{\varepsilon,\ ;\}$   \\
$CAB(Sentencia) = \{IDENT,\ IF,\ BEGIN\}$       \\
$CAB(Condicion) = \{TRUE,\ FALSE,\ IDENT\}$     \\
$CAB(Condicion') = \{EPS,\ AND\}$               \\
$CAB(Comparacion) = \{=,\ DIF\}$                \\

$SIG(ListaSentencias) = \{\$,\ END\}$           \\
$SIG(ListaSentencias') = \{\$,\ END\}$          \\
$SIG(Sentencia) = \{;,\ \$,\ END\}$             \\
$SIG(Condicion) = \{;,\ \$,\ ),\ END\}$         \\
$SIG(Comparacion) = \{AND,\ ;,\ \$,\ ),\ END\}$ \\
$SIG(Condicion') = \{;,\ \$,\ ),\ END\}$        \\

\medskip

La tabla LL(1) es:

\begin{center}
\begin{tabular}{|l|ccccccc|} \hline
                       & {\bf IDENT} & {\bf :=} & {\bf IF} & {\bf THEN} & {\bf BEGIN} & {\bf END} & {\bf TRUE} \\ \hline
{\em ListaSentencias}  & 1           &          & 1        &            & 1           &           &            \\
{\em ListaSentencias'} &             &          &          &            &             & 2         &            \\
{\em Sentencia}        & 4           &          & 5        &            & 6           &           &            \\
{\em Condici\'on}      & 9           &          &          &            &             &           & 7          \\
{\em Condici\'on'}     &             &          &          &            &             & 11        &            \\
{\em Comparaci\'on}    &             &          &          &            &             &           &            \\ \hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|l|cccccccc|} \hline
                       & {\bf FALSE} & {\bf $<>$} & {\bf AND} & {\bf ;} & {\bf (} & {\bf )} & {\bf $=$} & {\bf \$} \\ \hline
{\em ListaSentencias}  &             &            &           &         &         &         &           &          \\
{\em ListaSentencias'} &             &            &           & 3       &         &         &           & 2        \\
{\em Sentencia}        &             &            &           &         &         &         &           &          \\
{\em Condici\'on}      & 8           &            &           &         &         &         &           &          \\
{\em Condici\'on'}     &             &            & 10        & 11      &         & 11      &           & 11       \\
{\em Comparaci\'on}    &             & 13         &           &         &         &         & 12        &          \\ \hline
\end{tabular}
\end{center}